/**
 * FileName: Exercise1607.c
 * -------------------------------------------------------------------------------------------------------
 * 16.7 Give the height of the B trees that result when you insert the keys
 * `562, 221, 240, 771, 274, 233, 401, 273, 201` in Exercise 16.28 in that order into an initially empty tree,
 * for each value of $M > 2$.
 * -----------------------------------------------------------------------------------------------
 *
 *
 */
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

//Item相关
typedef int Key;
typedef int Value;
typedef struct Item* Item;

struct Item {
    Key key;
    Value value;
};

//注意：这些宏的参数是 Item* 类型，因此比较的是其内部的 key 成员
#define key(A) (A->key)
#define value(A) (A->value)
#define less(A, B)  ((A) < (B))
#define eq(A, B)    ((A) == (B))
#define exch(A, B) { Item t = A; A = B; B = t; }
#define NULLitem NULL

// #define M 10 //B树的阶
static int M;

//STnode相关
typedef struct STnode* link;
typedef struct {
    Key key;
    union {
        link next;
        Item item;
    } ref;
} entry;

struct STnode {
    entry* b;
    int m;
};

static link head;
static int N;
static int H;


//辅助函数声明
link NEW();
Item searchR(link, Key, int);
link insertR(link, Item, int);
link split(link);

//符号表操作声明
void STinit(int);
Item STsearch(Key);
void STinsert(Item);

//辅助函数实现
link NEW() {
    link x = malloc(sizeof(*x));
    x->m = 0;
    // 动态分配 entry 数组
    x->b = malloc(sizeof(entry) * M); // 使用 M_VAL
    return x;
}

link split(link h) {
    int j;
    link t = NEW();
    int split_idx = M/2; // 分裂点索引，也是拷贝键的索引
    for (j = 0; j < (M - split_idx); j++) {
        t->b[j] = h->b[split_idx+j];
    }
    t->m = M - split_idx;
    h->m = M/2;
    return t;
}

Item searchR(link h, Key v, int H) {
    int j;
    if (H == 0) {
        for (j = 0; j < h->m; j++) {
            if (eq(v, h->b[j].key)) {
                return h->b[j].ref.item;
            }
        }
    }
    if (H != 0) {
        for (j = 0; j < h->m; j++) {
            if ((j+1 == h->m) || less(v, h->b[j+1].key)) {
                return searchR(h->b[j].ref.next, v, H-1);
            }
        }
    }
    return NULLitem;
}

link insertR(link h, Item item, int H) {
    int i;
    int j;
    Key v = key(item);
    entry x;
    link t;
    link u;

    x.key = v;
    x.ref.item = item;

    if (H == 0) {
        for (j = 0; j < h->m; j++) {
            if (less(v, h->b[j].key)) {
                break;
            }
        }
    }

    if (H != 0) {
        for (j = 0; j < h->m; j++) {
            if ((j+1 == h->m) || less(v, h->b[j+1].key)) {
                t = h->b[j].ref.next;
                u = insertR(t, item, H-1);
                if (u == NULL) {
                    return NULL;
                }
                x.key = u->b[0].key;
                x.ref.next = u;
                j++;
                break;
            }
        }
    }

    (h->m)++;
    for (i = (h->m)-1; i > j; i--) {
        h->b[i] = h->b[i-1];
    }
    h->b[j] = x;
    if (h->m < M) {
        return NULL;
    }else {
        return split(h);
    }
}

//符号表操作实现
void STinit(int order) {
    M = order;
    head = NEW();
    H = 0;
    N = 0;
}

Item STsearch(Key v) {
    return searchR(head, v, H);
}

void STinsert(Item item) {
    link t;
    link u = insertR(head, item, H);
    if (u == NULL) {
        N++;
        return;
    }
    t = NEW();
    t->m = 2;
    t->b[0].key = head->b[0].key;
    t->b[0].ref.next = head;
    t->b[1].key = u->b[0].key;
    t->b[1].ref.next = u;

    head = t;
    H++;
    N++;
}




//测试函数部分
Item createItem(Key, Value);
void test_insert();
char* get_binary_9bit_string(int);

int main(int argc, char *argv[]) {
    test_insert();
    return 0;
}

Item createItem(Key key, Value value) {
    Item x = malloc(sizeof(*x));
    x->key = key;
    x->value = value;
    return x;
}

// Function to convert an integer to a 9-bit binary string
char* get_binary_9bit_string(int num) {
    // Declare a static character array.
    // Static ensures its memory persists after the function returns.
    // 10 characters: 9 bits + 1 for the null terminator ('\0')
    static char binary_string[10];

    // Loop from bit 8 down to bit 0
    for (int i = 8; i >= 0; i--) {
        // Determine the bit (0 or 1)
        int bit = (num >> i) & 1;
        // Convert the bit (integer 0 or 1) to its character representation ('0' or '1')
        binary_string[8 - i] = bit + '0'; // Store it in the correct position (0-indexed)
    }
    // Null-terminate the string
    binary_string[9] = '\0';

    return binary_string;
}


void test_insert() {
    // 使用八进制字面量表示这组数字
    // 每个以 '0' 开头的数字都会被编译器解释为八进制数
    int octal_numbers[] = {
        0562,
        0221,
        0240,
        0771,
        0274,
        0233,
        0401,
        0273,
        0201
    };

    // 计算数组中元素的数量
    int num_elements = sizeof(octal_numbers) / sizeof(octal_numbers[0]);

    // printf("使用八进制表示的数字数组 (括号内为对应的十进制值):\n");
    // for (int i = 0; i < num_elements; i++) {
    //     // %o 用于以八进制形式打印整数
    //     // %d 用于以十进制形式打印整数
    //     printf("0%o (十进制: %d)\n", octal_numbers[i], octal_numbers[i]);
    // }
    //
    // printf("-----------------------------------------------------------------\n");
    // printf("使用八进制表示的数字数组 (括号内为对应的二进制值):\n");
    // for (int i = 0; i < num_elements; i++) {
    //     // %o 用于以八进制形式打印整数
    //     printf("0%o (二进制: %s)\n", octal_numbers[i], get_binary_9bit_string(octal_numbers[i]));
    // }

    int j;
    for (j = 3; j < 11; j++) {
        STinit(j);
        for (int i = 0; i < num_elements; i++) {
            STinsert(createItem(octal_numbers[i], i+1));
        }
        printf("M = %d, 插入完成，节点总数 N = %d，B 树高度 H = %d\n", M, N, H);
    }

}
